package Graph.Medium;

import java.util.LinkedList;
import java.util.Queue;

public class LC1926 {
    /**
     * 利用广度优先遍历
     * 结果正确；但需要构建邻接矩阵，会超出内存限制
     */
    public static int nearestExit(char[][] maze, int[] entrance) {
        int nRows = maze.length;
        int nCols = maze[0].length;
        int nVerts = nRows * nCols;
        int[][] matrix = new int[nVerts][nVerts];
        for (int i = 0; i < nVerts; i++) matrix[i][i] = 1;
        // 构建无向无权图
        for (int row = 0; row < nRows; row++) {
            for (int col = 0; col < nCols; col++) {
                if (!(maze[row][col] == '.')) continue;
                int thisGridUid = getUid(row, col, nCols);
                int adjGridUid;
                // 只需考虑右侧和上侧邻接方格
                if (row + 1 < nRows && maze[row + 1][col] == '.') {
                    adjGridUid = getUid(row + 1, col, nCols);
                    matrix[thisGridUid][adjGridUid] = 1;
                    matrix[adjGridUid][thisGridUid] = 1;
                }
                if (col + 1 < nCols && maze[row][col + 1] == '.') {
                    adjGridUid = getUid(row, col + 1, nCols);
                    matrix[thisGridUid][adjGridUid] = 1;
                    matrix[adjGridUid][thisGridUid] = 1;
                }
            }
        }

        int entranceUid = getUid(entrance[0], entrance[1], nCols);
        Queue<int[]> queue = new LinkedList<>();
        queue.add(entrance);
        boolean[] visited = new boolean[nVerts];
        int level = 0;
        int thisLevelCount = 1, nextLevelCount = 0;
        while (!queue.isEmpty()) {
            int[] block = queue.poll();
            int blockUid = getUid(block[0], block[1], nCols);
            thisLevelCount--;
            visited[blockUid] = true;

            // 检查是否是出口
            if (checkIsBorder(block, nRows, nCols, entrance))
                return level;

            // 广度优先遍历
            for (int row = 0; row < nRows; row++) {
                for (int col = 0; col < nCols; col++) {
                    int uid = getUid(row, col, nCols);
                    if (matrix[blockUid][uid] > 0 && !visited[uid]) {
                        queue.add(new int[]{row, col});
                        nextLevelCount++;
                    }
                }
            }

            if (thisLevelCount == 0) { // 当前层遍历完毕
                thisLevelCount = nextLevelCount;
                nextLevelCount = 0;
                level++;
            }
        }

        return -1;
    }

    /**
     * 这个版本仍然基于广度优先遍历，但是不构建邻接矩阵
     */
    public static int nearestExitOptimized(char[][] maze, int[] entrance) {
        int nRows = maze.length;
        int nCols = maze[0].length;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(entrance);
        boolean[][] visited = new boolean[nRows][nCols];
        visited[entrance[0]][entrance[1]] = true;
        int level = 0;
        int thisLevelCount = 1, nextLevelCount = 0;
        while (!queue.isEmpty()) {
            int[] block = queue.poll();
            int row = block[0];
            int col = block[1];
            thisLevelCount--;

            // 检查是否是出口
            if (checkIsBorder(block, nRows, nCols, entrance))
                return level;

            // 广度优先遍历
            if (row + 1 < nRows && maze[row + 1][col] == '.' && !visited[row + 1][col]) {
                queue.add(new int[]{row + 1, col});
                visited[row + 1][col] = true; // 入队列时标记visited，可以避免超时 TODO 出队列时标记会导致超时，为什么？
                nextLevelCount++;
            }
            if (col + 1 < nCols && maze[row][col + 1] == '.' && !visited[row][col + 1]) {
                queue.add(new int[]{row, col + 1});
                visited[row][col + 1] = true;
                nextLevelCount++;
            }
            if (row - 1 >= 0 && maze[row - 1][col] == '.' && !visited[row - 1][col]) {
                queue.add(new int[]{row - 1, col});
                visited[row - 1][col] = true;
                nextLevelCount++;
            }
            if (col - 1 >= 0 && maze[row][col - 1] == '.' && !visited[row][col - 1]) {
                queue.add(new int[]{row, col - 1});
                visited[row][col - 1] = true;
                nextLevelCount++;
            }


            if (thisLevelCount == 0) { // 当前层遍历完毕
                thisLevelCount = nextLevelCount;
                nextLevelCount = 0;
                level++;
            }
        }

        return -1;
    }

    private static int getUid(int row, int col, int nCols) {
        return row * nCols + col;
    }

    private static boolean checkIsBorder(int[] coordinate, int nRows, int nCols, int[] entrance) {
        if (coordinate[0] == entrance[0] && coordinate[1] == entrance[1]) return false;
        if (coordinate[0] == 0 || coordinate[0] == nRows - 1 || coordinate[1] == 0 || coordinate[1] == nCols - 1)
            return true;
        else return false;
    }

    public static void main(String[] args) {
        char[][] maze = new char[][]{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}};
        System.out.println(nearestExitOptimized(maze, new int[]{1, 0}));
    }
}
